package algorithm.MonotonePriorityStack.leetcode_907;

import java.util.Stack;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int MOD = 1000000007;
        long ans = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                int temp = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                // 对每部分计算都进行取模，防止溢出
                long count = ((long)(i - temp) * (temp - left)) % MOD;
                ans = (ans + (count * arr[temp]) % MOD) % MOD;
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int temp = stack.pop();
            int left = stack.isEmpty() ? -1 : stack.peek();
            // 同样对清算阶段的计算进行取模
            long count = ((long)(n - temp) * (temp - left)) % MOD;
            ans = (ans + (count * arr[temp]) % MOD) % MOD;
        }

        return (int) (ans % MOD);
    }
}
